#include <vector>
#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
private:
    ListNode * reverse(ListNode * head)
    {
        ListNode * pre = nullptr;
        ListNode * cur = head;
        ListNode * nxt = cur->next;
        while(1)
        {
            cur->next = pre;
            pre = cur;
            cur = nxt;
            if(nxt == nullptr)
            {
                break;
            }
            nxt = nxt->next;
        }
        return pre;
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode * dummy = new ListNode(0,head);
        ListNode * pre = dummy;
        ListNode * end = dummy;

        while(end->next != nullptr)
        {
            for(int i = 0; i < k && end != nullptr; i++)
            {
                end = end->next;
            }
            if(end == nullptr)
            {
                break;
            }

            ListNode * start = pre->next;
            ListNode * nxt = end->next;
            end->next = nullptr;
            pre->next = reverse(start);
            start->next = nxt;

            pre = start;
            end = pre;
        }
        ListNode * result = dummy->next;
        delete dummy;
        return result;
    }
};

// 辅助函数：从vector创建链表
ListNode* createList(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    
    for (int i = 1; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    cout << "[";
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next != nullptr) cout << ",";
        cur = cur->next;
    }
    cout << "]";
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：题目示例1 [1,2,3,4,5], k = 2
    cout << "测试案例1: ";
    vector<int> nums1 = {1, 2, 3, 4, 5};
    int k1 = 2;
    ListNode* head1 = createList(nums1);
    cout << "head = ";
    printList(head1);
    cout << ", k = " << k1;
    ListNode* result1 = solution.reverseKGroup(head1, k1);
    cout << " -> ";
    printList(result1);
    cout << " (期望: [2,1,4,3,5])" << endl;
    deleteList(result1);
    
    // 测试案例2：题目示例2 [1,2,3,4,5], k = 3
    cout << "测试案例2: ";
    vector<int> nums2 = {1, 2, 3, 4, 5};
    int k2 = 3;
    ListNode* head2 = createList(nums2);
    cout << "head = ";
    printList(head2);
    cout << ", k = " << k2;
    ListNode* result2 = solution.reverseKGroup(head2, k2);
    cout << " -> ";
    printList(result2);
    cout << " (期望: [3,2,1,4,5])" << endl;
    deleteList(result2);
    
    // 测试案例3：k = 1 (不需要反转)
    cout << "测试案例3: ";
    vector<int> nums3 = {1, 2, 3, 4, 5};
    int k3 = 1;
    ListNode* head3 = createList(nums3);
    cout << "head = ";
    printList(head3);
    cout << ", k = " << k3;
    ListNode* result3 = solution.reverseKGroup(head3, k3);
    cout << " -> ";
    printList(result3);
    cout << " (期望: [1,2,3,4,5])" << endl;
    deleteList(result3);
    
    // 测试案例4：k等于链表长度
    cout << "测试案例4: ";
    vector<int> nums4 = {1, 2, 3, 4};
    int k4 = 4;
    ListNode* head4 = createList(nums4);
    cout << "head = ";
    printList(head4);
    cout << ", k = " << k4;
    ListNode* result4 = solution.reverseKGroup(head4, k4);
    cout << " -> ";
    printList(result4);
    cout << " (期望: [4,3,2,1])" << endl;
    deleteList(result4);
    
    // 测试案例5：k大于链表长度
    cout << "测试案例5: ";
    vector<int> nums5 = {1, 2, 3};
    int k5 = 5;
    ListNode* head5 = createList(nums5);
    cout << "head = ";
    printList(head5);
    cout << ", k = " << k5;
    ListNode* result5 = solution.reverseKGroup(head5, k5);
    cout << " -> ";
    printList(result5);
    cout << " (期望: [1,2,3])" << endl;
    deleteList(result5);
    
    // 测试案例6：单个节点
    cout << "测试案例6: ";
    vector<int> nums6 = {1};
    int k6 = 1;
    ListNode* head6 = createList(nums6);
    cout << "head = ";
    printList(head6);
    cout << ", k = " << k6;
    ListNode* result6 = solution.reverseKGroup(head6, k6);
    cout << " -> ";
    printList(result6);
    cout << " (期望: [1])" << endl;
    deleteList(result6);
    
    // 测试案例7：空链表
    cout << "测试案例7: ";
    vector<int> nums7 = {};
    int k7 = 2;
    ListNode* head7 = createList(nums7);
    cout << "head = ";
    printList(head7);
    cout << ", k = " << k7;
    ListNode* result7 = solution.reverseKGroup(head7, k7);
    cout << " -> ";
    printList(result7);
    cout << " (期望: [])" << endl;
    deleteList(result7);
    
    // 测试案例8：完全可以整除的情况 [1,2,3,4,5,6], k = 3
    cout << "测试案例8: ";
    vector<int> nums8 = {1, 2, 3, 4, 5, 6};
    int k8 = 3;
    ListNode* head8 = createList(nums8);
    cout << "head = ";
    printList(head8);
    cout << ", k = " << k8;
    ListNode* result8 = solution.reverseKGroup(head8, k8);
    cout << " -> ";
    printList(result8);
    cout << " (期望: [3,2,1,6,5,4])" << endl;
    deleteList(result8);
    
    return 0;
}